package other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 泛微20190611面试题：
 *   现有一int数组，将其拆分成为子数组A、B，使得Math.abs(sum(A) - sum(B))最小
 *   例如：给定数组：{1,5,3,4,7,6}
 *   得出结果：{1,3,4,5} {7,6}
 *
 * @author liuwanxiang
 * @version 2019/06/12
 */
public class MinimalDifference {

    /**
     * 将数组分割成差值最小的子集
     * 基本思路：暴力穷举，时间复杂度O(n)=2^n
     */
    private static void printTwoMinDiffGroups(int[] values) {
        int length = values.length;
        // 长度为length的二进制表示个数有1<<length个
        // 根据数组长度，构建标志位bit，1000 0000
        long allMasks = 1L << length;
        // min默认为int.max_value
        long min = Long.MAX_VALUE;
        // value用来记录最终拆分后的标志位bit
        long value = 0;
        // 依次循环，按照位的0/1之分，计算两个数组的差值，取diff最小的value
        // 此value即为数组拆分所要用到的标志位bit
        for (long i = allMasks - 1; i >= 0; i--) {
            int diff = 0;
            for (int j = 0; j < length; j++) {
                diff += (i & (1L << j)) == 0 ? values[j] : -values[j];
            }
            if (Math.abs(diff) < min) {
                min = Math.abs(diff);
                value = i;
            }
        }

        /*
         * 将上述计算得到的value值，与二进制表示相比较
         *
         * 1. value & (1 << j)) == 0
         * 2. ((value & (1 << j)) == (1 << j))
         */
        System.out.printf("原数组  %s 分割成两个和最接近的数组如下：\n", Arrays.toString(values));
        System.out.print("数组一的内容: ");
        for (int j = 0; j < length; j++) {
            System.out.print(((value & (1L << j)) == 0) ? values[j] + " " : "");
        }

        System.out.print("\n数组二的内容: ");
        for (int j = 0; j < length; j++) {
            System.out.print(((value & (1L << j)) == (1 << j)) ? values[j] + " " : "");
        }
        System.out.println("\n---------------------------------");
    }

    /**
     * 先求和半值，后进行凑单，时间复杂度O(n)=n
     */
    private static void methodWithList(int[] values) {

        List<Integer> leftList = new ArrayList<>();
        List<Integer> rightList = new ArrayList<>();

        // 从小到大排序
        // 快速排序，O(n) = nlogn
        Arrays.sort(values);

        // 求得数组和及数据和半值
        // 循环次数=n
        int totalSum = 0;
        int rightSum = 0;
        for (int v : values) {
            leftList.add(v);
            totalSum += v;
        }
        int halfSum = totalSum / 2;

        // 循环次数=n
        for (int i = leftList.size() - 1; i >= 0; i--) {
            if (rightSum + leftList.get(i) <= halfSum) {
                rightSum += leftList.get(i);
                rightList.add(leftList.remove(i));
                if (Math.abs(rightSum - halfSum) < leftList.get(0)) {
                    break;
                }
            }
        }

        System.out.println("子数组一：" + leftList);
        System.out.println("子数组二：" + rightList);
    }

    public static void main(String[] args) {
        // 暴力穷举
        printTwoMinDiffGroups(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10});

        // 先求和半值，后进行凑单
        methodWithList(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
                21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40});
    }

}
